/******************************************************************************
ISYS 1078 / 1079 — Information Retrieval
Assignment #1

Student Name: [ Rui, Wang ]
Student ID: [ 3171459 ]
CSIT username: [ rwang ]
*******************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "func.h"
#include <ctype.h>

#define NIL &leafNode
TermNode leafNode = {"NIL",-1,NULL,NIL,NIL,0,Black,-1,NULL};
LexTree root = NIL;

void LexIndexInit(LexIndex *lexIndex)
{
	lexIndex->head = root;
}

/*Function Name: rotateLeft*/
/* Purpose: Left rotation, node x moved to left */
/*Reference:  original code Author: Stefan Fruhner     */
/* http://newcenturycomputers.net/projects/rbtree.html */
void rotateLeft(LexElement *x)
{
   LexTree y = x->Right;

   /* establish x->right link */
   x->Right = y->Left;
   if (y->Left != NIL)
       y->Left->parent = x;

   /* establish y->parent link */
   if (y != NIL) 
      y->parent = x->parent;

   if (x->parent) 
   {
       if (x == x->parent->Left)
           x->parent->Left = y;
       else
           x->parent->Right = y;
   } 
   else 
   {
       root = y;
   }

   /* link x and y */
   y->Left = x;

   if (x != NIL)
      x->parent = y;
}


/*Function Name: rotateRight*/
/* Purpose: node x moved to right */
/*Reference:  original code Author: Stefan Fruhner      */
/* http://newcenturycomputers.net/projects/rbtree.html */
void rotateRight(LexElement *x) 
{
    LexTree y = x->Left;

    /* establish x->left link */
    x->Left = y->Right;
    if (y->Right != NIL) y->Right->parent = x;

    /* establish y->parent link */
    if (y != NIL) y->parent = x->parent;
    if (x->parent) 
	{
        if (x == x->parent->Right)
            x->parent->Right = y;
        else
            x->parent->Left = y;
    } 
	else 
	{
        root = y;
    }

    /* link x and y */
    y->Right = x;
    if (x != NIL) x->parent = y;
}



/*Function Name: inserFixup                                        */
/* Purpose: maintain red-Black tree balance after inserting node x */
/*Reference:  original code Author: Stefan Fruhner                 */
/* http://newcenturycomputers.net/projects/rbtree.html            */
void insertFixup(LexElement *x)
{
    /* check Red-Black properties */
    while (x != root && x->parent->Color == Red) 
	{
        /* violation, to check whether x has a grandParent node */
        if (x->parent == x->parent->parent->Left) 
		{
            LexTree y = x->parent->parent->Right;
            /*check the color of x's uncle node 'y'*/
            if (y->Color == Red) 
			{
                /* if uncle is RED , reset x parent and its uncle's color to BLACK
                   reset grandParent color to red*/
                x->parent->Color = Black;
                y->Color = Black;
                x->parent->parent->Color = Red;
                x = x->parent->parent;
            } 
			else 
			{
                /* uncle is BLACK */
                if (x == x->parent->Right) 
				{
                    /* make x a left child */
                    x = x->parent;
                    rotateLeft(x);
                }

                /* recolor and rotate */
                x->parent->Color = Black;
                x->parent->parent->Color = Red;
                rotateRight(x->parent->parent);
            }
        } 
		else 
		{
            /* mirror image of above code */
            LexTree y = x->parent->parent->Left;
            if (y->Color == Red)
			{

                /* uncle is RED */
                x->parent->Color = Black;
                y->Color = Black;
                x->parent->parent->Color = Red;
                x = x->parent->parent;
            } 
			else 
			{
                /* uncle is BLACK */
                if (x == x->parent->Left) 
				{
                    x = x->parent;
                    rotateRight(x);
                }
                x->parent->Color = Black;
                x->parent->parent->Color = Red;
                rotateLeft(x->parent->parent);
            }
        }
    }
    root->Color = Black;
}

void TermInsert(LexIndex *lexIndex, char *word, LexElement** newTerm, int docId)
{
	LexTree curr, parent, X;
	root = lexIndex->head;
	curr = lexIndex->head;
	parent = 0;

	while(curr != NIL)
	{
		if(strcmp(word, curr->term) == 0)
		{
			*newTerm = curr;
	/*		if(curr->currDocId != docId)
				curr->freq_t++;*/
			/*curr->freq_t++;*/
			return;
		}
		parent = curr;
		
		if(strcmp(word, curr->term) < 0)
			curr = curr->Left;
		else
			curr = curr->Right;
	}
		if((X = malloc(sizeof(TermNode))) == NULL)
		{
			fprintf(stderr,"Memory Allocation Failed! (TermNode)\n");
			return;
		}
		
		X->term = malloc((strlen(word)+1)*sizeof(char));
		strcpy(X->term, word);
		X->freq_t = 0;
		X->head = NULL;
		X->currDocId = docId;
		X->currIvtPtr = X->head;
		X->Right = NIL;
		X->Left = NIL;
		X->parent = parent;
		X->Color = Red;
		*newTerm = X;
	
		if(parent)
		{
			if(strcmp(word, parent->term) < 0)
				parent->Left = X;
			else
				parent->Right = X;
		}
		else
			root = X;
			
		insertFixup(X);
		
		lexIndex->head = root;
		
		return;
}

void DocIndexInit(DocIndex *docIndex)
{
	docIndex->root = NULL;
}

void DocInsert(DocIndex *docIndex, int id, char *docNum)
{
	DocTree curr, prev, newnode;
	curr = docIndex->root;

	while(curr != NULL)
	{
		prev = curr;
		
		if( strcmp(curr->docNum, docNum)<0)
			curr = curr->Right;
		else
			curr = curr->Left;
	}

	if((newnode = malloc(sizeof(DocNode))) == NULL)
	{
		fprintf(stderr,"Memory Allocation Failed!(DocInsert)");
		return;
	}
	
	newnode->docId = id;
	newnode->docNum = malloc((strlen(docNum)+1)*sizeof(char));
	strcpy(newnode->docNum, docNum);
	newnode->Left = newnode->Right = NULL;
	
	if(docIndex->root == NULL)
		docIndex->root = newnode;
	else if(strcmp(prev->docNum, docNum) > 0)
		prev->Left = newnode;
	else
		prev->Right = newnode;
}

int IvtListInsert(LexElement* term, int docId, int pos)
{
	IvtList curr, prev, newIvtNode;
	PosList newPos, prevPos, currPos;
	int freq_t;
	/*curr = term->head;*/
	curr = term->currIvtPtr;
	prev = NULL;
	freq_t = 1;
/*	
	while(curr != NULL && (curr->docId < docId) )
	{	
		freq_t++;
		prev = curr;
		curr = curr->next;
	}
	
	term->freq_t = freq_t;*/
	
	/*same docID, add sub postions */
	if(curr != NULL && (curr->docId == docId) )
	{   
		curr->freq_dt++;
		
		newPos = malloc(sizeof(PosNode));
		newPos->pos = pos;
		newPos->next = NULL;
		currPos = curr->head;
	
		while(currPos != NULL)
		{	
			prevPos = currPos;
			currPos = currPos->next;
		}
		
		prevPos->next = newPos;

		/*testing*/
		
		return 0;
	}
	else
	{   /*check and self-increase freq_t of current term*/
		term->freq_t++;
		
		if((newIvtNode = malloc(sizeof(IvtNode))) == NULL)
		{
			fprintf(stderr,"Memory Allocation Failed! (IvtListInsert 2)\n");
			return -1;
		}
		
		newIvtNode->docId = docId;
		newIvtNode->freq_dt = 1;
	/*	newIvtNode->next = curr;*/
		newIvtNode->next = NULL;
		
		newPos = malloc(sizeof(PosNode));
		newPos->pos = pos;
		newPos->next = NULL;
		newIvtNode->head = newPos;

/*		if(prev == NULL)
			term->head = newIvtNode;
		else
			prev->next = newIvtNode;
*/	
		/*testing*/
		if(term->head == NULL)
			term->head = newIvtNode;
		else
		{
			prev = term->currIvtPtr;
			prev->next = newIvtNode;
		
		}
			term->currIvtPtr = newIvtNode;
		
		return 0;
	}
}

void GenerateDocMap(DocTree DT, FILE *fp, Doc *curr)
{
    
	if(DT != NULL)
	{	
		GenerateDocMap(DT->Left, fp, curr);

		curr->docId = DT->docId;
		strcpy(curr->docNum, DT->docNum);

		fwrite(curr, sizeof(Doc), 1, fp);
		GenerateDocMap(DT->Right, fp, curr);
	}
	
	return;
}

void GenerateLexAndIvtFile(LexTree LT, FILE *fp_lex, FILE *fp_ivt, Term *curr)
{
	int ppos;
	
	if(LT != NIL)
	{
		GenerateLexAndIvtFile(LT->Left, fp_lex, fp_ivt, curr);
		
		/*Lexicon file process, get the pointer to the inverted lists position*/
		/*if the file is empty, ppos is 0*/
		ppos = ftell(fp_ivt);

		strcpy(curr->term,LT->term);
		curr->ppos = ppos;
		fwrite(curr,sizeof(Term),1,fp_lex);

		/*create inverted posting list file*/
		GenerateIvtLists(LT->head, fp_ivt, LT->freq_t);
		
		GenerateLexAndIvtFile(LT->Right, fp_lex, fp_ivt, curr);
	}
	
}

void GenerateIvtLists(IvtList IL, FILE *fp, int freq_t)
{
	IvtList curr, next;
	PosList currPos, nextPos;
	curr = IL;
	fwrite(&freq_t, sizeof(int), 1, fp);
	while(curr != NULL)
	{
		next = curr->next;
		fwrite(&curr->docId, sizeof(int), 1, fp);
		fwrite(&curr->freq_dt, sizeof(int),1, fp);
		
		currPos = curr->head;
		
		while(currPos != NULL)
		{
			nextPos = currPos->next;
			fwrite(&currPos->pos, sizeof(int), 1, fp);
			currPos = nextPos;
		}
		
		curr = next;
	}
	/*set end tag of posting*/
}

void GenerateFiles(DocIndex *docIndex, LexIndex *lexIndex)
{
	FILE *fp_map, *fp_lex, *fp_ivt;
	Term *currTerm;
	Doc *currDoc;
	
	currTerm = malloc(sizeof(Term));
	currDoc = malloc(sizeof(Doc));
	
	/*1st generate MAP file*/
	fp_map = fopen("map","wb");
    GenerateDocMap(docIndex->root,fp_map, currDoc);
	fclose(fp_map);

	/*2nd generate lexicon and invlists together*/
	fp_lex = fopen("lexicon","wb");
	fp_ivt = fopen("invlists","wb");
	
	GenerateLexAndIvtFile(lexIndex->head, fp_lex, fp_ivt, currTerm);
	
	fclose(fp_lex);
	fclose(fp_ivt);
	free(currTerm);
	free(currDoc);
}

void ToLowerCase(char *str)
{
	int p = 0;

	while(str[p] != '\0')
	{	
		if(str[p] >= 'A' && str[p] <= 'Z')
		{
			str[p] += 32;
		}
		p++;
	}
}

int IsDigit(char c)
{
	if(c >='0' && c <= '9')
		return 1;
	else
		return 0;
}

int IsAlpha(char c)
{
	if( c >= 'a' && c <= 'z')
		return 1;
	else 
		return 0;
}

int IsDelimiter(char c)
{
	char *str = " \n\t,.?!;-_=+><:\"(){}[]\'#$\\^&*~`'@/|%";
	
	while(*str != '\0')
	{
		if(*str++ == c)
			return 1;
	}
	return 0;
}


int DataParse(int mode, char *filename, DocIndex *docIndex, LexIndex *lexIndex)
{
	FILE *fp_src;
	int length;
	char *buf;
	int pos, docId;
	char *pcur, *pdest, *pbegin, *pend, *str;
	char word[W_MAX_LEN];
	LexTree newTerm = NULL;
	pcur = NULL;
	pdest = NULL;
	pbegin = NULL;
	pend = NULL;
	str = NULL;
		
	fp_src = fopen(filename,"r");

    if(fp_src == NULL)
    {
      fprintf(stderr,"cannot open source file %s!\n",filename);
      return -1;
    }

	fseek(fp_src, 0, SEEK_END);
	length = ftell(fp_src)+1;
	rewind(fp_src);
	
	if((buf = malloc(length+1)) == NULL)
	{
		fprintf(stderr, "\n Memory Allocation Faild! (DataParse Failed!)");
		return -1;
	}
	
	fread(buf, 1, length, fp_src);
	buf[length-1] = '\0';
	fclose(fp_src);
	ToLowerCase(buf);

	fprintf(stdout,"Parsing...\n");
	str = word;
	pcur = buf;
	
	docId = 0;
	
	while((pdest = strstr(pcur, "</doc>")) != NULL)
	{
		pbegin = strstr(pcur, "<docno>");
		pend = strstr(pbegin, "</docno>");
		
		*(pend) ='\0';

		DocInsert(docIndex,docId,pbegin+7);
		
		/*Process word*/
		pbegin = strstr(pend+8, "<text>");
		pend = strstr(pbegin, "</text>");
		pbegin+=6;
		pos = 0;
		
		while(pbegin < pend)
		{
			if(IsDelimiter(*pbegin))
			{
				if(str >word)
				{
					*(str) = '\0';
				
					/*mode for -p argument*/
					if(mode == 0)
						fprintf(stdout,"%s ", word);
						
					/*insert word*/
					TermInsert(lexIndex, word, &newTerm, docId);
					IvtListInsert(newTerm, docId, ++pos);
					/*add inverted posting node to this word term*/
					str = word;
				}
			}
			else if((IsAlpha(*pbegin)) || (IsDigit(*pbegin)))
			{
				*str = *pbegin;
				str++;
			}
			pbegin++;
		}
		
		if(str > word)
		{
			*(str) ='\0';
	
			TermInsert(lexIndex, word, &newTerm, docId);
			IvtListInsert(newTerm, docId, ++pos);
			str = word;
		}
		
		/*process next doc*/
		docId++;
		pcur = pdest+1;
	}
	
	free(buf);
	pcur = NULL;
	pdest = NULL;
	pbegin = NULL;
	str = NULL;
	pend = NULL;

	fprintf(stdout,"Finish Parsing...\n");
    fprintf(stdout,"Generating Files...\n");
	GenerateFiles(docIndex, lexIndex);
	fprintf(stdout,"Finished Files Creation...\n");

	return 0;
}

void DestroyDocTree(DocTree T)
{
	if(T != NULL)
	{
		DestroyDocTree(T->Left);
		DestroyDocTree(T->Right);
		free(T->docNum);
		free(T);
	}
}

void DestroyLexTree(LexTree T)
{
	if(T != NIL)
	{
		DestroyLexTree(T->Left);
        /*destroy Inverted  LinkList*/
		DestroyIvtList(T->head);
	    DestroyLexTree(T->Right);
		
		free(T->term);
        free(T);
    }
}

void DestroyIvtList(IvtList IL)
{
	IvtList curr,prev;
	curr = IL;

   while(curr != NULL)
   {      
      	prev = curr;
        /*destroy pos linked list*/
		DestroyPosList(curr->head);
      	curr = curr->next;
      	free(prev);    
   }
}

void DestroyPosList(PosList PL)
{
	PosList curr,prev;
	curr = PL;

   while(curr != NULL)
   {      
      prev = curr;
      /*destroy pos linked list*/
      curr = curr->next;
      free(prev);    
   }
}

void DestroyTask(DocIndex *docIndex, LexIndex *lexIndex)
{
	DocTree DT;
	LexTree LT;

    DT = docIndex->root;
	LT = lexIndex->head;
	
	DestroyDocTree(DT);
	DestroyLexTree(LT);
}